package leetcode.editor.cn.dsa09_doublequeue;
//给定一个字符串，逐个翻转字符串中的每个单词。

import java.util.Deque;
import java.util.LinkedList;

public class ReverseWordsInAString151_2 {
    public static void main(String[] args) {
        ReverseWordsInAString151_2.Solution solution = new ReverseWordsInAString151_2().new Solution();
        System.out.println(solution.reverseWords("the sky is blue"));
        System.out.println(solution.reverseWords("  hello world!  "));
        System.out.println(solution.reverseWords("a good   example"));
        System.out.println(solution.reverseWords("  Bob    Loves  Alice   "));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解法三：双端队列解法思路分析
         * 1.往双端队列头部依次存入每个单词
         *   以空格为单词分界，将单词字符存入缓冲区
         *   从缓冲区取出单词存入双端队列头部
         *   注意过滤掉首尾、单词间多余空格
         * 2.从双端队列头部依次取出每个单词
         *   使用join方法，将空格拼接到每个单词之间
         *   注意不要遗漏最后一个单词
         *
         * @param s
         * @return
         */
        public String reverseWords(String s) {
            int len = s.length();
            // 定义双端队列，也可以用数组实现的ArrayDeque
            Deque<String> deque = new LinkedList<>();
            StringBuilder word = new StringBuilder();
            for (int i = 0; i < len; i++) {
                char c = s.charAt(i);
                if (c != ' ') {
                    word.append(c);
                } else {
                    if (word.length() > 0) { // 到达了单词结尾
                        // 将单词添加到队列的头部
                        deque.addFirst(word.toString());
                        // 清空缓冲区
                        word.setLength(0);
                    }
                }
            }
            if (word.length() > 0) {
                deque.addFirst(word.toString());
            }
            // 默认从队头进行遍历
            return String.join(" ", deque);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}